package cn.edu.ncepu;

import java.util.Random;

/**
 * 费马素性测试（Fermat Primality Test）
 * 注意：存在卡迈克尔数（如561、341）会被误判为素数
 */
public class FermatPrimalityTest {

    /**
     * 二进制快速幂算法（复刻Python逻辑）
     * @param base 底数
     * @param power 指数
     * @return base^power 的结果
     */
    public static long binaryExponentiation(long base, long power) {
        long power2 = 1;
        long r = 1;
        long p = base;
        // 循环条件：power2左移1位后 <= power
        while ((power2 = power2 << 1) <= power) {
            p = p * p;
            // 位运算判断当前位是否为1
            if ((power2 & power) != 0) {
                r *= p;
            }
        }
        return r;
    }

    /**
     * 费马素性测试
     * @param n 待测试的数
     * @return true：大概率为素数；false：确定为合数
     */
    public static boolean isPrim(long n) {
        // 边界处理：n <= 4 时直接判断
        if (n <= 4) {
            return n == 2 || n == 3;
        }

        Random random = new Random();
        // 随机选取5个底数a进行测试
        for (int i = 0; i < 5; i++) {
            // 生成 [2, n] 范围内的随机整数（对应Python的random.randint(2, n)）
            long a = 2 + random.nextLong(n - 1); // nextLong(n-1) 生成 [0, n-2)，+2后为 [2, n)，若需严格包含n可调整
            // 计算 a^(n-1) mod n
            long result = binaryExponentiation(a, n - 1) % n;
            // 若不满足费马小定理，说明是合数
            if (result != 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // 测试用例，与Python一致
        System.out.println(isPrim(10000));   // 合数，预期false
        System.out.println(isPrim(911));    // 素数，预期true
        System.out.println(isPrim(561));    // 卡迈克尔数，预期true（误判）
        System.out.println(isPrim(341));    // 卡迈克尔数，预期true（误判）
    }
}